#include <iostream>
#include <array>

using std::cout;
using std::endl;
using std::array;

// 求最长非降子序列长度
/*
    4, 1, 7, 2, 7, 2 , 5, 3, 6
    1, 2, 7 / 1, 2, 5 

状态转移方程：
    dp[0] = 1
    dp[1] = arr[1] > arr[1 - 1] ? dp[1 - 1] + 1 : 1 = 1
    dp[2] = arr[2] > arr[2 - 1] ? dp[2 - 1] + 1 : 1 = 2
    dp[3] = arr[3] > arr[3 - 1] ? dp[3 - 1] + 1 : 1 = 

    dp[i] = max(arr[i] > arr[i - j] ? dp[i - j] + 1 : 1)

*/

int cnt = 0;
int pre = 0;

template<size_t N>
void bf(array<int, N> &arr, int i)
{
    int maxLen = 0;
    array<int, N> dp;
    dp[0] = 1;
    for(int i{1}; i < arr.size(); i++){
        // dp[i] = arr[i] > arr[i - 1] ? dp[i - 1] + 1 : dp[i - 1];
        int max = 0;
         for(int j{i - 1}; j >= 0; j--){
            if(arr[i] > arr[j]){
                max = std::max(dp[j], max);
            }
        }
        dp[i] = max + 1;
        if(dp[i] > maxLen) maxLen = dp[i];
    }

    cout << "bf: " << maxLen << endl;
}

int main(int args, char *argv[])
{
    array<int, 9> arr = {5, 3, 4, 1, 8, 6, 7, 10};
    bf(arr, 0);
    return 0;
}